[clang-tidy] Add a clang-tidy check for possible inefficient vector operations

[hokein]

Summary

The "performance-inefficient-vector-operation" check finds vector oprations in
for-loop statements which may cause multiple memory reallocations.

This is the first version, only detects typical for-loop:

std::vector<int> v;
for (int i = 0; i < n; ++i) {
  v.push_back(i);
}

// or

for (int i = 0; i < v2.size(); ++i) {
  v.push_back(v2[i]);
}

We can extend it to handle more cases like for-range loop in the future.

[hokein]

Fix a small nit.

[Eugene.Zelenko]

Isn't such analysis is path-sensitive and should be implemented in Static Analyzer?

Please mention this check in docs/ReleaseNotes.rst (in alphabetical order).

docs/clang-tidy/checks/performance-inefficient-vector-operation.rst

7

I think will be good idea to use std::vector, and enclose it and push_back in ``.

[hokein]

Mention the check in Release note.

[hokein]

In D31757#720351, @Eugene.Zelenko wrote:

Isn't such analysis is path-sensitive and should be implemented in Static Analyzer?

This check is more like a flow-sensitive analysis IMO, which can be supported by clang-tidy.

Please mention this check in docs/ReleaseNotes.rst (in alphabetical order).

Done. I think we could add this tip in the add_new_check.py script, so that developers don't forget about it ;)

[aaron.ballman]

In D31757#721129, @hokein wrote:

In D31757#720351, @Eugene.Zelenko wrote:

Isn't such analysis is path-sensitive and should be implemented in Static Analyzer?

This check is more like a flow-sensitive analysis IMO, which can be supported by clang-tidy.

It can be supported by clang-tidy, but your patch isn't doing it. I think the check would be improved substantially by improving the analysis.

clang-tidy/performance/InefficientVectorOperationCheck.cpp

22

Why does this check only focus on vector? Other containers allow you to preallocate space for their elements or lend themselves to inefficient operations.

Also, this should be checking ::std::vector instead.

32

This isn't paying attention to what is being reserved.

46–50

These conditions seem rather restrictive -- why should you not get the same issue with a range-based for loop?

53–54

I'm really not keen on this. It will catch trivial cases, so there is some utility, but this will quickly fall apart with anything past the trivial case.

69–71

These asserts should come with string literal messages, though I think they can be removed entirely (I don't think there's a value add here).

74

Why the llvm:: qualifier?

80

Do not use auto, and the formatting is off.

92

Surround push_back with quotes.

test/clang-tidy/performance-inefficient-vector-operation.cpp

53

I'd like to see a test where you reserve 5 elements and then loop for 10 elements.

[hokein]

Address review comments.

[hokein]

clang-tidy/performance/InefficientVectorOperationCheck.cpp

22

Why does this check only focus on vector? Other containers allow you to preallocate space for their elements or lend themselves to inefficient operations.

Only a few std containers (vector, unordered_map, unorder_set) provide the preallocate ability ("reserve") to users. vector is the most widely used container with these inefficient operations in the real world.

Yes, we could extend this check to support other containers, but it will make the check more complicated (in the future, I plan to support for-range loops and for loops with iterators, and use other elegant fix-it solutions like "range insert" or "range constructor" in some specific cases rather than merely inserting reserve statements). So I think it makes more sense to make this check only focus on vector.

32

Good catch. Added a test for it.

46–50

Yeah, this is intended. We want to match typical for-loops with counters here. For-range loop will be supported in the future.

53–54

The motivation of this check is to find code patterns like for (int i = 0; i < n; ++i) { v.push_back(i); } and clean them in our codebase (we have lots of similar cases). These are all cases we want to support. Using hasParent is a simple and sufficient way to do it IMO.

test/clang-tidy/performance-inefficient-vector-operation.cpp

53

Even for this case, the check will also ignore it.

[aaron.ballman]

clang-tidy/performance/InefficientVectorOperationCheck.cpp

53–54

I'm not convinced of the utility without implementing this in a more sensitive way. Have you run this across any large code bases and found that it catches issues?

[hokein]

clang-tidy/performance/InefficientVectorOperationCheck.cpp

53–54

Yeah, the check catches ~2800 cases (regexp shows ~17,000 total usages) in our internal codebase. And all caught cases are what we are interested in. It would catch more if we support for-range loops and iterator-based for-loops.

[aaron.ballman]

clang-tidy/performance/InefficientVectorOperationCheck.cpp

53–54

I wasn't worried about it not triggering often enough, I was worried about it triggering too often because of the lack of sensitivity. If you randomly sample some of those 2800 cases, do they reserve the space in a way that your check isn't catching?

[hokein]

clang-tidy/performance/InefficientVectorOperationCheck.cpp

53–54

Ok, I see your concern now, thanks for pointing it out.

I have read through these caught cases. The results look reasonable. Most cases (> 95%) are what we expected, the code pattern is like vector<T> v; for (...) { v.push_back(...); } where the vector definition statement and for-loop statement are consecutive. Another option is to make the check more strict (only detects the consecutive code pattern).

[aaron.ballman]

clang-tidy/performance/InefficientVectorOperationCheck.cpp

53–54

Okay, that sounds like it has utility then. Thank you for clarifying!

[hokein]

Improve the way of detecting pre-allocation usage before the loop.

[hokein]

friendly ping @alexfh.

clang-tidy/performance/InefficientVectorOperationCheck.cpp

53–54

I improved the way of catching the preallocations before the loop. Could you take a look again?

[aaron.ballman]

clang-tidy/performance/InefficientVectorOperationCheck.cpp

82

Perhaps you could support other comparisons, but not attempt to generate a fix-it for them? It seems odd that this would trigger for < but not <=, but I can see why you'd not want to figure out the reserve call for !(foo >= 10).

84

Thinking out loud, but, what happens if the loop end expression has some hidden complexity to it? e.g.,

for (int i = 0; i < i + 1; ++i) { // This is a "creative" loop.
  v.push_back(i);
}

85

Can you add a test case for post-increment (all of your tests use pre-increment)? Also, count-down loops seem reasonable to support as well, no?

for (int i = 10; i >= 0; --i) {
  v.push_back(i);
}

87–88

You should update the documentation to mention that this check only worries about a for loop with a single statement in it. It will be surprising that this code does not trigger the same diagnostic:

for (...) {
  std::cout << i;
  v.push_back(i);
}

96–97

We don't usually add this test in to our check calls; why are you adding it here?

99

Might as well make this a reference rather than a pointer (simplifies code elsewhere).

101–105

Formatting (I would recommend running clang-format over the patch).

110–112

I'm not certain what types are being used here. Can you turn AllVectorVarRefs into something with an explicit type so that I can know what Ref's type is?

118

identified -> identify

clang-tidy/performance/InefficientVectorOperationCheck.h

21

Drop the hyphen in for loops.

docs/clang-tidy/checks/performance-inefficient-vector-operation.rst

8

The docs should talk more about the limitations of the check (like how many statements it can contain, etc).

[hokein]

Address review comments.

[hokein]

Thanks for the comments.

clang-tidy/performance/InefficientVectorOperationCheck.cpp

82

We could support other comparisons in the future. I think it is a good start to just support < in the first version as < usage happens more frequently than other comparisons.

Added a fixme.

84

Good point. It will copy the expr "i+1" to "reserve" parameter. This kind of case should not be existed, but it is safer to filter out this case.

96–97

It will prevent some unexpected things happened when the translation unit fails to compile.

We had a few experiences before. We encountered some misbehavior of some checks (e.g. https://reviews.llvm.org/rL294578) with a non-compilable TU, and then we added this statement to avoid the misbehavior.

[aaron.ballman]

clang-tidy/performance/InefficientVectorOperationCheck.cpp

96–97

I think that this should be moved up into whatever layer calls check(), because it does not seem like the checks are actually valid if the TU has had a fatal error. However, that doesn't have to be part of this patch.

110–112

I may not have been clear -- I don't mean that the variable name should contain type information, I mean that the type should not be automatically deduced. We only use auto when the type is spelled explicitly in the initialization or is otherwise obvious from context (like range-based for loops).

[hokein]

Explicit the type.

clang-tidy/performance/InefficientVectorOperationCheck.cpp

110–112

I'd prefer to use auto to initialize AllVectorVarRefExprs, as its type is SmallPtrSet<const DeclRefExpr *, 16>, which is a long and noisy name. Using auto can increases readability here.

[aaron.ballman]

clang-tidy/performance/InefficientVectorOperationCheck.cpp

110–112

It doesn't increase readability when someone reviewing the code has no idea what types are involved and has to ask you for clarification. auto should only be used when the type is obvious from the context or spelling the type is *really* noisy. A single level of template goop is a very small amount of noise.

117

Formatting (and you can use auto here once you correct the type above).

[hokein]

Address remaining comments.

[aaron.ballman]

LGTM!

[hokein]

@alexfh, I'm submitting the patch now. If you have following comments, I'm happy to address them afterwards.

[chapuni]

Does it work for targeting msvc?
See also; http://bb.pgr.jp/builders/test-clang-tools-msc-x64-on-i686-linux-RA/builds/1043

Appeased in r300545. Would it be happier if it worked with "-target x86_64-win32"?

[hokein]

@chapuni, thanks for the workaround. It makes sense to make it work for targeting msvc. Will fix it in a follow-up.

[alexfh]

Awesome, thanks! A few late comments inline.

clang-tools-extra/trunk/clang-tidy/performance/InefficientVectorOperationCheck.cpp

56 ↗

(On Diff #95534)

It might make sense to make the list of types configurable to support custom vector-like types.

65 ↗

(On Diff #95534)

Loops with emplace_back would suffer from the same issue.

131 ↗

(On Diff #95534)

No need to namespace-qualify StringRef and Lexer.

133 ↗

(On Diff #95534)

Actual LangOptions should be used instead of a default-constructed instance. Same below.

143 ↗

(On Diff #95534)

Please remove the trailing period.

clang-tidy/performance/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS support)
 
 add_clang_library(clangTidyPerformanceModule
   FasterStringFindCheck.cpp
   ForRangeCopyCheck.cpp
   ImplicitCastInLoopCheck.cpp
   InefficientStringConcatenationCheck.cpp
+  InefficientVectorOperationCheck.cpp
   PerformanceTidyModule.cpp
   TypePromotionInMathFnCheck.cpp
   UnnecessaryCopyInitialization.cpp
   UnnecessaryValueParamCheck.cpp
 
   LINK_LIBS
   clangAST
   clangASTMatchers
   clangBasic
   clangLex
   clangTidy
   clangTidyUtils
   )

clang-tidy/performance/InefficientVectorOperationCheck.h

+//===--- InefficientVectorOperationCheck.h - clang-tidy----------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_PERFORMANCE_INEFFICIENT_VECTOR_OPERATION_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_PERFORMANCE_INEFFICIENT_VECTOR_OPERATION_H
+
+#include "../ClangTidy.h"
+
+namespace clang {
+namespace tidy {
+namespace performance {
+
+/// Finds possible inefficient `std::vector` operations (e.g. `push_back`) in
+/// for-loops that may cause unnecessary memory reallocations.
+///
+/// For the user-facing documentation see:
+/// http://clang.llvm.org/extra/clang-tidy/checks/performance-inefficient-vector-operation.html
+class InefficientVectorOperationCheck : public ClangTidyCheck {
+public:
+  InefficientVectorOperationCheck(StringRef Name, ClangTidyContext *Context)
+      : ClangTidyCheck(Name, Context) {}
+  void registerMatchers(ast_matchers::MatchFinder *Finder) override;
+  void check(const ast_matchers::MatchFinder::MatchResult &Result) override;
+};
+
+} // namespace performance
+} // namespace tidy
+} // namespace clang
+
+#endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_PERFORMANCE_INEFFICIENT_VECTOR_OPERATION_H

clang-tidy/performance/InefficientVectorOperationCheck.cpp

+//===--- InefficientVectorOperationCheck.cpp - clang-tidy------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "InefficientVectorOperationCheck.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/Lex/Lexer.h"
+
+using namespace clang::ast_matchers;
+
+namespace clang {
+namespace tidy {
+namespace performance {
+
+void InefficientVectorOperationCheck::registerMatchers(MatchFinder *Finder) {
+  const auto VectorDecl = cxxRecordDecl(hasName("std::vector"));
+  const auto VectorDefaultConstructorCall = cxxConstructExpr(
+      hasType(VectorDecl),
+      hasDeclaration(cxxConstructorDecl(isDefaultConstructor())));
+  const auto VectorVarDefStmt =
+      declStmt(
+          hasSingleDecl(varDecl(hasInitializer(VectorDefaultConstructorCall))
+                            .bind("vector_var_def")))
+          .bind("vector_var_stmt");
+  const auto ReserveCall = cxxMemberCallExpr(
+      callee(cxxMethodDecl(hasName("reserve"))), on(hasType(VectorDecl)));
+  const auto PushBackCall =
+      cxxMemberCallExpr(callee(cxxMethodDecl(hasName("push_back"))),
+                        on(hasType(VectorDecl)))
+          .bind("push_back_call");
+  const auto LoopVarInit =
+      declStmt(hasSingleDecl(varDecl(hasInitializer(integerLiteral(equals(0))))
+                                 .bind("init_loop_var")));
+  const auto RefersToLoopVar = ignoringParenImpCasts(
+      declRefExpr(to(varDecl(equalsBoundNode("init_loop_var")))));
+
+  Finder->addMatcher(
+      forStmt(
+          hasLoopInit(LoopVarInit),
+          hasCondition(binaryOperator(hasOperatorName("<"),
+                                      hasLHS(RefersToLoopVar),
+                                      hasRHS(expr().bind("loop_end_expr")))),
+          hasIncrement(unaryOperator(hasOperatorName("++"),
+                                     hasUnaryOperand(RefersToLoopVar))),
+          hasBody(anyOf(compoundStmt(statementCountIs(1), has(PushBackCall)),
+                        PushBackCall)),
+          hasParent(compoundStmt(unless(has(ReserveCall)),
+                                 has(VectorVarDefStmt))))
+          .bind("for_loop"),
+      this);
+}
+
+void InefficientVectorOperationCheck::check(
+    const MatchFinder::MatchResult &Result) {
+  const auto *ForLoop = Result.Nodes.getNodeAs<ForStmt>("for_loop");
+  const auto* PushBackCall =
+      Result.Nodes.getNodeAs<CXXMemberCallExpr>("push_back_call");
+  const auto* LoopEndExpr =
+      Result.Nodes.getNodeAs<Expr>("loop_end_expr");
+  const auto* VectorVarDef =
+      Result.Nodes.getNodeAs<VarDecl>("vector_var_def");
+
+  assert(ForLoop);
+  assert(PushBackCall);
+  assert(LoopEndExpr);
+
+  const auto *PushBackCallerObject =
+      llvm::dyn_cast<DeclRefExpr>(PushBackCall->getImplicitObjectArgument());
+  // Ignore for-loops in which the push_back isn't referenced by the targeted
+  // vector var definition.
+  if (!PushBackCallerObject || PushBackCallerObject->getDecl() != VectorVarDef)
+    return;
+
+  const auto* SM= Result.SourceManager;
+  llvm::StringRef LoopEndSource = clang::Lexer::getSourceText(
+      CharSourceRange::getTokenRange(LoopEndExpr->getSourceRange()), *SM,
+      clang::LangOptions());
+  llvm::StringRef VectorVarName = clang::Lexer::getSourceText(
+      CharSourceRange::getTokenRange(
+          PushBackCall->getImplicitObjectArgument()->getSourceRange()),
+      *SM, clang::LangOptions());
+  std::string ReserveStmt =
+      (VectorVarName + ".reserve(" + LoopEndSource + ");\n").str();
+
+  diag(PushBackCall->getLocStart(),
+       "push_back is called inside a loop; "
+       "consider pre-allocating the vector capacity before the loop.")
+      << FixItHint::CreateInsertion(ForLoop->getLocStart(), ReserveStmt);
+}
+
+} // namespace performance
+} // namespace tidy
+} // namespace clang

clang-tidy/performance/PerformanceTidyModule.cpp

 //===--- PeformanceTidyModule.cpp - clang-tidy ----------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "../ClangTidy.h"
 #include "../ClangTidyModule.h"
 #include "../ClangTidyModuleRegistry.h"
 #include "FasterStringFindCheck.h"
 #include "ForRangeCopyCheck.h"
 #include "ImplicitCastInLoopCheck.h"
 #include "InefficientStringConcatenationCheck.h"
+#include "InefficientVectorOperationCheck.h"
 #include "TypePromotionInMathFnCheck.h"
 #include "UnnecessaryCopyInitialization.h"
 #include "UnnecessaryValueParamCheck.h"
 
 namespace clang {
 namespace tidy {
 namespace performance {
 
 class PerformanceModule : public ClangTidyModule {
 public:
   void addCheckFactories(ClangTidyCheckFactories &CheckFactories) override {
     CheckFactories.registerCheck<FasterStringFindCheck>(
         "performance-faster-string-find");
     CheckFactories.registerCheck<ForRangeCopyCheck>(
         "performance-for-range-copy");
     CheckFactories.registerCheck<ImplicitCastInLoopCheck>(
         "performance-implicit-cast-in-loop");
     CheckFactories.registerCheck<InefficientStringConcatenationCheck>(
         "performance-inefficient-string-concatenation");
+    CheckFactories.registerCheck<InefficientVectorOperationCheck>(
+        "performance-inefficient-vector-operation");
     CheckFactories.registerCheck<TypePromotionInMathFnCheck>(
         "performance-type-promotion-in-math-fn");
     CheckFactories.registerCheck<UnnecessaryCopyInitialization>(
         "performance-unnecessary-copy-initialization");
     CheckFactories.registerCheck<UnnecessaryValueParamCheck>(
         "performance-unnecessary-value-param");
   }
 };

docs/ReleaseNotes.rst

 Improvements to clang-tidy
 --------------------------
 
 - New `cert-dcl58-cpp
   <http://clang.llvm.org/extra/clang-tidy/checks/cert-dcl58-cpp.html>`_ check
 
   Finds modification of the ``std`` or ``posix`` namespace.
 
-- Improved `cppcoreguidelines-no-malloc 
+- Improved `cppcoreguidelines-no-malloc
   <http://clang.llvm.org/extra/clang-tidy/checks/cppcoreguidelines-no-malloc.html>`_ check
 
   Allow custom memory management functions to be considered as well.
 
 - New `readability-misleading-indentation
   <http://clang.llvm.org/extra/clang-tidy/checks/readability-misleading-indentation.html>`_ check
 
   Finds misleading indentation where braces should be introduced or the code should be reformatted.
- New `modernize-return-braced-init-list
   <http://clang.llvm.org/extra/clang-tidy/checks/modernize-return-braced-init-list.html>`_ check
 
   Finds and replaces explicit calls to the constructor in a return statement by
   a braced initializer list so that the return type is not needlessly repeated.
 
 - Support clang-formatting of the code around applied fixes (``-format-style``
   command-line option).
 
+- New `performance-inefficient-vector-operation
+  <http://clang.llvm.org/extra/clang-tidy/checks/performance-inefficient-vector-operation.html>`_ check
+
+  Finds possible inefficient vector operations in for-loops that may cause
+  unnecessary memory reallocations.
+
 Improvements to include-fixer
 -----------------------------
 
 The improvements are...
 
 Improvements to modularize
 --------------------------
 
 The improvements are...

docs/clang-tidy/checks/list.rst

.. toctree::
    modernize-use-transparent-functors
    modernize-use-using
    mpi-buffer-deref
    mpi-type-mismatch
    performance-faster-string-find
    performance-for-range-copy
    performance-implicit-cast-in-loop
    performance-inefficient-string-concatenation
+   performance-inefficient-vector-operation
    performance-type-promotion-in-math-fn
    performance-unnecessary-copy-initialization
    performance-unnecessary-value-param
    readability-avoid-const-params-in-decls
    readability-braces-around-statements
    readability-container-size-empty
    readability-delete-null-pointer
    readability-deleted-default

docs/clang-tidy/checks/performance-inefficient-vector-operation.rst

+.. title:: clang-tidy - performance-inefficient-vector-operation
+
+performance-inefficient-vector-operation
+========================================
+
+Finds possible inefficient `std::vector` operations (e.g. `push_back`) that may
+cause unnecessary memory reallocations.
+
+.. code-block:: c++
+
+  std::vector<int> v;
+  for (int i = 0; i < n; ++i) {
+    v.push_back(n);
+    // This will trigger the warning since the push_back may cause multiple
+    // memory reallocations in v. This can be avoid by inserting a reserve(n)
+    // statment before the for statment.
+  }

test/clang-tidy/performance-inefficient-vector-operation.cpp

+// RUN: %check_clang_tidy %s performance-inefficient-vector-operation %t -- -format-style=llvm --
+
+typedef int size_t;
+
+namespace std {
+template <class T>
+class vector {
+ public:
+  typedef T* iterator;
+  typedef const T* const_iterator;
+  typedef T& reference;
+  typedef const T& const_reference;
+  typedef size_t size_type;
+
+  explicit vector();
+  explicit vector(size_type n);
+
+  void push_back(const T& val);
+  void reserve(size_t n);
+  size_t size();
+  const_reference operator[] (size_type) const;
+  reference operator[] (size_type);
+};
+} // namespace std
+
+void f(std::vector<int>& t) {
+  {
+    std::vector<int> v;
+    // CHECK-FIXES: v.reserve(10);
+    for (int i = 0; i < 10; ++i)
+      v.push_back(i);
+      // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: push_back is called inside a loop; consider pre-allocating the vector capacity before the loop
+  }
+  {
+    std::vector<int> v;
+    // CHECK-FIXES: v.reserve(t.size());
+    for (size_t i = 0; i < t.size(); ++i) {
+      v.push_back(t[i]);
+      // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: push_back is called
+    }
+  }
+  {
+    std::vector<int> v;
+    // CHECK-FIXES: v.reserve(t.size() - 1);
+    for (size_t i = 0; i < t.size() - 1; ++i) {
+      v.push_back(t[i]);
+    } // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: push_back is called
+  }
+
+  // ---- Non-fixed Cases ----
+  {
+    std::vector<int> v;
+    v.reserve(20);
+    // CHECK-FIXES-NOT: v.reserve(10);
+    // There is a "reserve" call already.
+    for (int i = 0; i < 10; ++i) {
+      v.push_back(i);
+    }
+  }
+  {
+    std::vector<int> v(20);
+    // CHECK-FIXES-NOT: v.reserve(10);
+    // v is not constructed with default constructor.
+    for (int i = 0; i < 10; ++i) {
+      v.push_back(i);
+    }
+  }
+  {
+    std::vector<int> v;
+    // CHECK-FIXES-NOT: v.reserve(10);
+    // For-loop is not started with 0.
+    for (int i = 1; i < 10; ++i) {
+      v.push_back(i);
+    }
+  }
+  {
+    std::vector<int> v;
+    // CHECK-FIXES-NOT: v.reserve(t.size());
+    // v isn't referenced in for-loop body.
+    for (size_t i = 0; i < t.size(); ++i) {
+      t.push_back(i);
+    }
+  }
+  {
+    std::vector<int> v;
+    int k;
+    // CHECK-FIXES-NOT: v.reserve(10);
+    // For-loop isn't a fixable loop.
+    for (size_t i = 0; k < 10; ++i) {
+      v.push_back(t[i]);
+    }
+  }
+  {
+    std::vector<int> v;
+    int k;
+    // CHECK-FIXES-NOT: v.reserve(10);
+    // For-loop isn't a fixable loop.
+    for (size_t i = 0; i < 10; ++k) {
+      v.push_back(t[i]);
+    }
+  }
+}